package com.sise.Backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 *      面试题 08.07. 无重复字符串的排列组合
 *      无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
 *
 *
 *      示例1:
 *      输入：S = "qwe"
 *      输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
 */
public class _interview_08_07_permutation {

    public String[] permutation(String S) {
        char[] chars = S.toCharArray();
        List<String> resultList = new ArrayList<>();
        boolean[] used = new boolean[S.length()];
        StringBuffer path = new StringBuffer();

        dfs(chars, resultList, path, used);

        // 遍历 List，通过 get() 将数值一一赋值到数组中
        String[] result = new String[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }

    /**
     *
     * @param chars     题目提供的原始数值
     * @param result    将所有可能都存入目标值
     * @param path      当前路径、当前选择
     * @param used      当前坐标索引是否被使用
     */
    private void dfs(char[] chars, List<String> result, StringBuffer path, boolean[] used) {
        if (path.length() == chars.length) {
            result.add(new String(path));
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (!used[i]) {
                used[i] = true;
                path.append(chars[i]);

                // 这里并不用考虑位置问题，因为这里使用 used[] 控制当前位置是否已被使用
                dfs(chars, result, path, used);
                used[i] = false;
                path.deleteCharAt(path.length() - 1);

            }
        }
    }
}
